class Solution {

    static search(arr, target) {
        let left = 0
        let right = arr.length - 1
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2)

            if (arr[mid] === target) {
                return mid
            }else if (arr[mid] < target) {
                left = mid + 1
            }else if (arr[mid] > target) {
                right = mid - 1
            }
        }
        
        return -1
    }

    static searchByRecursion(arr, target) {
        return Solution._recursion(arr, target, 0, arr.length - 1)
    }

    static _recursion(arr, target, left, right) {
        if (left >= right) {
            return -1
        }

        const mid = left + Math.floor((right - left) / 2)

        if (arr[mid] === target) {
            return mid
        }else if (arr[mid] < target) {
            return Solution._recursion(arr, target, mid + 1, right)
        }else if (arr[mid] > target) {
            return Solution._recursion(arr, target, left, mid - 1)
        }
    }
}

let test = function(arr, fun, target) {
    const result = fun(arr, target)
    if (result != -1) {
        console.log(`[${arr}]第${result}位 = ${target}`)
    }else {
        console.log(`[${arr}]中没有${target}`)
    }
}

let n = [-1, 0, 3, 5, 9, 12]
test(n, Solution.searchByRecursion, 9)
test(n, Solution.searchByRecursion, 10)
test(n, Solution.search, 9)
test(n, Solution.search, 10)
